package pers.qianyu.month_202012.date_20201220;

import org.junit.*;

/**
 * 172. 阶乘后的零
 * https://leetcode-cn.com/problems/factorial-trailing-zeroes/
 *
 * @author mizzle rain
 * @date 2020-12-20 20:18
 */
public class TrailingZeroes {
    // 寻找 5 为因子的个数
    public int trailingZeroes(int n) {
        int count = 0;
        for (int i = 5; i <= n; i += 5) {
            int cur = i;
            while (cur % 5 == 0) {
                count++;
                cur /= 5;
            }
        }
        return count;
    }

    public int trailingZeroes2(int n) {
        int count = 0;
        for (int i = 5; i <= n; i += 5) {
            int d = 5;
            while (i % d == 0) {
                count++;
                d *= 5;
            }
        }
        return count;
    }

    // 更简洁的解法
    public int trailingZeroes3(int n) {
        int count = 0;
        long d = 5;
        while (n >= d) {
            count += (n / d);
            d *= 5;
        }
        return count;
    }

    @Test
    public void test1() {
        int result = new TrailingZeroes().trailingZeroes3(5);
        Assert.assertEquals(result, 1);
    }

    @Test
    public void test2() {
        int result = new TrailingZeroes().trailingZeroes3(3);
        Assert.assertEquals(result, 0);
    }

    @Test
    public void test3() {
        int result = new TrailingZeroes().trailingZeroes3(30);
        Assert.assertEquals(result, 7);
    }
}
